package com.johann.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
// 可以用暴力求解 但时间复杂度不满足要求
public class T4_FindMedianSortedArrays {
    // 偶数even 奇数odd
    //
    static class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 先定义长度
            int len1 = nums1.length, len2 = nums2.length;
            // 全等于0
            if (len1 == 0 && len2 == 0) {
                return 0.0;
            }
            // 其中一个等于0 len1
            if (len1 == 0) {
                return len2 % 2 == 1 ? nums2[len2 / 2] : (nums2[len2 / 2 - 1] + nums2[len2 / 2]) / 2.0;
            }
            // 其中一个等于0 len2
            if (len2 == 0) {
                return len1 % 2 == 1 ? nums1[len1 / 2] : (nums1[len1 / 2 - 1] + nums1[len1 / 2]) / 2.0;
            }
            // 都不为空
            // [1 3 5]  [2 4 6 7]
            // 暴力，两数组合并，取中值  -- 不合要求
            // 双指针遍历数组
            int idx1 = 0, idx2 = 0;
            int midIndex = (len1 + len2) / 2;
            int midIndexEven = midIndex - 1;
            List<Integer> mergeArr = new ArrayList<>();
            // 若为奇数： 直接就是数组中的元素
            // [1 3 5] midIndex=1
            // [2 4]
            // 1 2 3 4 5 6 7
            if((len1 + len2) % 2 == 1){
                while (true) {
                    while ((idx1 < len1) && nums1[idx1] <= nums2[idx2]) {
                        mergeArr.add(nums1[idx1]);
                        idx1++;
                        if (mergeArr.size() - 1 == midIndex) {
                            return mergeArr.get(midIndex);
                        }
                    }
                    // 超出界限
                    while (idx2 < len2 && nums2[idx2] <= nums1[idx1]) {
                        mergeArr.add(nums2[idx2]);
                        idx2++;
                        if (mergeArr.size() - 1 == midIndex) {
                            return mergeArr.get(midIndex);
                        }
                    }
                    // 超出界限
                }
            }
            else{
                // 当偶数时
                // [2]
                // [4]
                while (true) {
                    while (idx1 < len1 && nums1[idx1] <= nums2[idx2]) {
                        mergeArr.add(nums1[idx1]);
                        idx1++;
                        if (mergeArr.size() - 1 == midIndex) {
                            return  (mergeArr.get(midIndex) + mergeArr.get(midIndexEven)) / 2.0;
                        }
                    }
                    while (idx2 < len2 && nums2[idx2] <= nums1[idx1]) {
                        mergeArr.add(nums2[idx2]);
                        idx2++;
                        if (mergeArr.size() - 1 == midIndex) {
                            return (mergeArr.get(midIndex) + mergeArr.get(midIndexEven)) / 2.0;
                        }
                    }
                }
            }
        }
        public double findMedianSortedArrays02(int[] nums1, int[] nums2){
            ArrayList<Integer> merArr = new ArrayList<>(nums1.length+nums2.length);
            for (int i : nums1) {
                merArr.add(i);
            }
            for (int i : nums2) {
                merArr.add(i);
            }
            int len = merArr.size();
            if (len == 0)  return 0;
            merArr.sort(Comparator.naturalOrder());
            return len%2==1 ? merArr.get(len/2): (merArr.get(len/2-1)+merArr.get(len/2))/2.0;
        }
        }
    // 暴力解法

        public static void main(String[] args) {
            System.out.println(new Solution().findMedianSortedArrays02(new int[]{},new int[]{1,3,5}));
            System.out.println(new Solution().findMedianSortedArrays02(new int[]{1,3,5},new int[]{}));
            System.out.println(new Solution().findMedianSortedArrays02(new int[]{1},new int[]{6,7})); // 第一种方法不可
            System.out.println(new Solution().findMedianSortedArrays02(new int[]{1,3},new int[]{6}));


        }
}


